/*****************************************************************************
*  @file     Example.h                                                       *
*  @brief    搜索旋转排序数组                                                              *
*                                                                            *
*  @author   kerwin                                                          *
*  @email    jiawei24714.com                                                 *
*  @version  1.0.0.1                                                         *
*  @date     2021/06/17 09:17:55                                             *
*                                                                            *
*----------------------------------------------------------------------------*
*  Remark         : Description                                              *
*----------------------------------------------------------------------------*
*  Change History :                                                          *
*  <Date>     | <Version> | <Author>    | <Description>                      *
*----------------------------------------------------------------------------*
*  2021/06/17 | 1.0.0.1   | kerwin      | Create file                        *
*----------------------------------------------------------------------------*
*                                                                            *
*****************************************************************************/


#include<bits/stdc++.h>
using namespace std;


/**
 * @brief 暴力搜索
 */
class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++){
            if(nums[i]==target)return i;
        }
        return -1;
    }
};


/**
 * @brief 二分查找
 */
class Solution1 {
public:
    int biSearch(vector<int>& nums, int start, int end, int target){
        if(end-start==1){
            if(target == nums[start])return start;
            return -1;
        }
        if(end <= start)return -1;
        int mid = (start+end)/2;
        if(nums[mid] > nums[start]){
            if(target == nums[mid])return mid;
            if(target>=nums[start] && target<nums[mid])return biSearch(nums, start, mid, target);
            return biSearch(nums, mid+1, end, target);
        }
        else {
            if(target == nums[mid])return mid;
            if(target <= nums[end-1] && target>nums[mid])return biSearch(nums, mid+1, end, target);
            return biSearch(nums, start, mid, target);
        }
    }

    int search(vector<int>& nums, int target) {
        return biSearch(nums, 0, nums.size(), target);
    }
};

int main(){
    cout << "Hello,world" << endl;
    return 0;
}